/*
这是一个哈夫曼树(最优二叉树)的实现

*/

#include "huffman_tree.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct hf_node_t {
  int parent, right, left; // 父节点 左孩子 有孩子
  double weight;           // 权重
};

static void _create(hf_tree tree, int n);

// 从提供的字符权重表来创建huffman树
hf_tree huffman_create(const double *array_weight, int n) {
  if (n <= 0)
    return NULL;

  int node_count = 2 * n - 1; // 哈夫曼树总节点数，n就是叶子结点

  // 0号不用, 便于计算,正好是2倍关系
  hf_tree tree = malloc(sizeof(struct hf_node_t) * (node_count + 1));
  if (tree == NULL)
    return NULL;

  //初始化哈夫曼树的所有节点, 2n个:其中0节点不使用
  for (int i = 1; i < node_count + 1; i++) {
    (tree + i)->parent = (tree + i)->left = (tree + i)->right = 0;
    if (i <= n) // 数组前一半存初始化为节点信息
      (tree + i)->weight = *(array_weight - 1 + i);
    else // 数组后一半留给结合后生成的父节点使用
      (tree + i)->weight = .0;
  }

  _create(tree, n);

  return tree;
}

// 构建哈夫曼树的过程是数组前一半节点,生成后一般父节点的过程
static void _create(hf_tree tree, int n) {
  // 遍历权值数组,构建二叉树
  double min1, min2; // 当前结合需要的两个最小权值
  int idx1, idx2;    // 记录最小权值值索引

  // n个节点,需要n-1次结合
  for (int unite = 1; unite < n; unite++) {
    min1 = min2 = __DBL_MAX__;
    idx1 = idx2 = 0;
    // 每次扩大查找范围1,因为每次循环会多生成了1个父节点
    for (int index = 1; index < n + unite; index++) {
      // 排除已经结合的节点
      if (tree[index].parent == 0 && tree[index].weight < min1) {
        min2 = min1;
        idx2 = idx1;
        min1 = tree[index].weight; // 排除已经结合的节点后,找到的最小值
        idx1 = index;
      } else {
        if (tree[index].parent == 0 && tree[index].weight < min2) {
          min2 = tree[index].weight; // 排除已经结合的节点后,找到的次小值
          idx2 = index;
        }
      }
    }

    //将找到的2个节点结合,将结合新生成的根节点依次放入tree数组的空位置.空位置从n+1后开始
    tree[idx1].parent = n + unite;
    tree[idx2].parent = n + unite;
    // 更新父节点信息
    tree[n + unite].weight = tree[idx1].weight + tree[idx2].weight;
    tree[n + unite].left = idx1;
    tree[n + unite].right = idx2;
  }
}

void huffman_destory(hf_tree tree) { free(tree); }

// 将字符编码字符串化到encoding数组中
void huf_code(hf_tree tree, char *encoding[], int n) {
  char bits[n + 1];  // 每个字符编码位数不会超过叶子节点个数
  int parent, child; // 循环查找中的父子关系(数组下标)

  // n 个被编码的字符
  for (int i = 1; i <= n; i++) {
    parent = tree[i].parent;
    child = i;
    char *p = bits;

    // 在整个数组中不断寻找父节点,直到父节点为0
    while (parent != 0) {
      if (child == tree[parent].left) // 当前元素是父节点的左节点,编码为0
        *p++ = '0';
      else if (child == tree[parent].right) // 当前元素是父节点的右节点,编码为1
        *p++ = '1';

      // 父节点作为子节点
      child = parent;
      // 继续寻找父节点
      parent = tree[parent].parent;
    }

    // 字符串化, 这时的编码还是反向的,需要翻转一下
    *p = '\0';
    strrev(bits);

    // printf("%s\n", temp);
    char *encoded = malloc(strlen(bits) + 1);
    memcpy(encoded, bits, strlen(bits) + 1);
    encoding[i - 1] = encoded;
  }
}
